package com.hy.stack.monotoneStack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class NextLargestElement02 {

    /**
     * 503.下一个更大元素II
     * 力扣题目链接
     *
     * 给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
     *
     * 示例 1:
     *
     * 输入: [1,2,1]
     * 输出: [2,-1,2]
     * 解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
     *
     * 思路
     * 做本题之前建议先做739. 每日温度 和 496.下一个更大元素 I。
     *
     * 这道题和739. 每日温度也几乎如出一辙。
     *
     * 不同的时候本题要循环数组了。
     *
     * 关于单调栈的讲解我在题解739. 每日温度中已经详细讲解了。
     *
     * 本篇我侧重与说一说，如何处理循环数组。
     *
     * 相信不少同学看到这道题，就想那我直接把两个数组拼接在一起，然后使用单调栈求下一个最大值不就行了！
     *
     * 确实可以！
     *
     * 讲两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以了。
     *
     *
     * @return
     */
    public static int [] nextGreaterElements(int [] nums){
        //边界判断
        if(nums == null || nums.length == 0){
            return new int[]{-1};
        }
        //栈中存放的是nums中的元素下标
        Stack<Integer> st = new Stack<>();
        // 存放结果
        int [] res = new int[nums.length];
        // 数据填充   默认初始化-1
        Arrays.fill(res,-1);
        int len = nums.length;
        for (int i = 0; i < len * 2; i++) {
            while (!st.isEmpty() && nums[i % len] > nums[st.peek()]){
                // 更新 res
                res[st.peek()] = nums[i%len];
                // 弹出栈顶元素
                st.pop();
            }
            st.push(i % len);
        }
        return res;
    }

    public static void main(String[] args) {
        int [] nums = {4,1,2,4};

        System.out.println("res: "+ Arrays.toString(nextGreaterElements(nums)));
    }
}
